package algorithms.leaning.class08;

import common.util.MyUtil;

/**
 * 对于非负数组 [899,765,3,5,7,9]
 * 1、准备10个桶
 * 2、找到最大的数的位数
 * 3、分别按个、十、百位从左到右按顺序入桶，然后再按桶的顺序从里面拿出数字
 * 4、处理完毕则数组排序完毕
 *
 * @author guichang
 * @date 2021/6/6
 */
@SuppressWarnings("all")
public class Code3_桶排序_基数排序 {
    public static void main(String[] args) {
        int[] array = MyUtil.createRandomArray(10, 1, 10000);
        radixSort(array);
        MyUtil.print("排序后: ");
        MyUtil.printInt(array);
    }

    public static void radixSort(int[] array) {
        // 边界条件
        if (array == null || array.length < 2) {
            return;
        }
        // 桶长度
        int radix = 10;
        // 原始数组长度
        int length = array.length;
        int[] help = new int[length];
        // 有几位数就出入桶几次
        for (int i = 0; i < maxNumberLength(array); i++) {
            // 计数数组
            int[] count = new int[radix];
            for (int j = 0; j < length; j++) {
                // array[j]第i+1位的数字
                int indexValue = indexValue(array[j], i);
                count[indexValue]++;
            }
            // 累加和
            for (int j = 1; j < count.length; j++) {
                count[j] += count[j - 1];
            }
            // 从右往左遍历
            for (int j = length - 1; j >= 0; j--) {
                // array[j]第i+1位的数字
                int indexValue = indexValue(array[j], i);
                // indexValue的数量
                int nums = count[indexValue];
                // 直接填充到辅助数组的相应位置
                help[nums - 1] = array[j];
                // 计数数组的数量-1
                count[indexValue]--;
            }
            // 复制回原数组
            for (int j = 0; j < length; j++) {
                array[j] = help[j];
            }
        }
    }

    /**
     * 数组中最大数的位数
     * 比如：3879 就返回4
     */
    public static int maxNumberLength(int[] array) {
        int max = Integer.MIN_VALUE;
        for (int a : array) {
            max = Math.max(max, a);
        }
        int length = 0;
        while (max != 0) {
            length++;
            max /= 10;
        }
        return length;
    }

    /**
     * num中第index+1位是多少，index从0开始
     *
     * @param num   3456
     * @param index 2
     * @return 4
     */
    public static int indexValue(int num, int index) {
        return ((num / ((int) Math.pow(10, index))) % 10);
    }


}